package it.unisa.ingegneria.tdp.esercitazione4;

import java.util.*;
/**
 * Classe che si occupa di implementare le funzionalità del Btree
 * 
 */

public class BTree <K extends Comparable<K>, V> implements Tree <K , V> {

	private TreeNode<K,V> root;
	private int t; // grado minimo
	private String s="";	 
	 
	/**
	 * Costruttore della classe
	 * 
	 * @param t parametro per impostare il grado minimo
	 */
	 public BTree(int t){
		this.t=t;
		root=null;
	}
	 
	 
	 /**
	  * Metodo per verificare se l'albero è vuoto
	  * 
	  * @return valore booleano che indica se l'abero è vuoto (TRUE) o non vuoto (FALSE)
	  */
	 public boolean isEmpty(){
		
		return (root==null||root.getSize()==0);
	}
	

	/**
	 * Metodo per richiamare la visita dell'albero
	 */
	 public void visit(){
		visitBT(root,0,s);
	}

	/**
	 * Metodo concreto per la visita dell'albero
	 * 
	 * @param node Nodo di partenza per la visita
	 * @param i	   intero che indica la profondità del nodo che si sta visitando
	 * @param ind  intero che indica la corretta indendazione della visita
	 */
	 
	 private void visitBT(TreeNode<K,V> node,int i,String ind){
		
		if(node==null)
			return;
		
		if(node.isLeaf()){
			System.out.print(ind+node.toString()+"\n");
			s="";	
		}
		else
			System.out.print(ind+node.toString());
		
		for(int j=0;j<node.getChildren().size();j++){	
			s="";
			if(j==0)
				i++;
				
			for(int z=0;z<i;z++)
			 s+="\t";	
			
			visitBT(node.getChildren().get(j),i,s);
		}
			
		
	}

	/**
	 * Metodo per l'inserimento di una nuova chiave nel BTree rispettando la logica della struttura
	 * 
	 * @param key chiave dell'elemento TInfo da inserire
	 * @param value valore dell'elemento TInfo da inserire
	 * 
	 */
	 @Override
	 public void insert(K key, V value) {

		TInfo<K, V> info=new TInfo<K,V>(key,value);

		if(root==null){
			root=new TreeNode<K,V>(t);
			root.addKey(root.getSize(), info);
		}else if(root.getSize()==(2*t-1)){
			TreeNode<K,V> newRoot=new TreeNode<K,V>(t);
			newRoot.addChild(0,root);
			newRoot.setLeaf(false);
			splitChild(newRoot,0);
			root=newRoot;			
			insertNonFull(root, info);
		}else
			insertNonFull(root,info);

	}

	 
	/**
	 * Metodo privato di supporto al metodo insert, si occupa dell'inserimento di un nuovo TInfo in un nodo non pieno
	 *  
	 * @param node nodo in cui inserire
	 * @param info oggetto TInfo da inserire nel nodo
	 */

	private void insertNonFull(TreeNode<K,V> node, TInfo<K,V> info) {
		
		int a = 0;
		int b = node.getSize();
		ArrayList<TInfo<K,V>> keys = node.getKeys();
		
		
		while (a < b) {
			int pivot = (a + b) / 2;
			int res = info.getKey().compareTo(keys.get(pivot).getKey());
			if (res < 0)
				b = pivot;
			else
				a = pivot + 1;
		}

		if (node.isLeaf()) {
		
			node.addKey(a, info);

		} else {
			
			if (node.getChildren().get(a).getSize() == 2 * t - 1) {
				splitChild(node, a);
				if (info.getKey().compareTo(node.getKeys().get(a).getKey()) > 0)
					a++;
			}
			insertNonFull(node.getChildren().get(a), info);
		}
	}


	/**
	 * Metodo privato di supporto ai metodi insert e insertNonFull, si occupa di distribuire le chiavi di un nodo su più nodi
	 * 
	 * @param node padre del figlio da dividere
	 * @param childToSplit intero che indica l'indice del figlio da dividere
	 */

	private void splitChild(TreeNode<K,V> node, int childToSplit) {
		
		TreeNode<K,V> z = new TreeNode<K,V>(t);
		TreeNode<K,V> y = node.getChildren().get(childToSplit);
		z.setLeaf(y.isLeaf());
			
		for (int i = 0; i < t - 1; i++){
			z.addKey(i, y.getKeys().get(t));
			y.removeKey(t);
	
			
		}


		if (!y.isLeaf()) {
			for (int i = 0; i < t; i++)
				z.addChild(i, y.getChildren().get(t+i));
			
			for (int i = 0; i < t; i++)
				y.removeChild(t);
		}

		//inserisco la chiave mediana in node e aggiungo il riferimento a z
		
		node.addChild(childToSplit + 1, z);
		
		node.addKey(childToSplit, y.getKeys().get(t - 1));
		
		y.removeKey(t - 1);
		
	
	}


	/**
	 * Metodo per cancellare una chiave da un BTree
	 * 
	 * @param key chiave da cancellare
	 */

	@Override
	public void delete(K key) {
		if(root!=null){
			deleteNonMin(root,key);
		if(root.getSize()==0 && root.getChildren().size()>0)
		root=root.getChildren().get(0);// se cancello la radice, il primo figlio della vecchia radice diventa la nuova radice

		}

	}

	/**
	 * Metodo per ricercare un elemento tramite chiave
	 * 
	 * @param key chiave da ricercare
	 * @return value dell'oggetto TInfo che ha come chiave key
	 */
	@Override
	public V search(K key) {
		if(root==null)
			return null;

		return searchRec(root,key);

	}
	
	/**
	 * Metodo concreto per effettuare la ricerca in modo ricorsivo di una chiave
	 * 
	 * @param root nodo in cui cercare
	 * @param key chiave da ricercare
	 * @return value dell'oggetto TInfo che ha come chiave key
	 */
	private V searchRec(TreeNode<K,V> root, K key) {
		if (root == null||root.getSize()==0)
			return null;
		
		else {
			int a = 0;
			int b = root.getSize();
			ArrayList<TInfo<K,V>> keys = root.getKeys();
			// Binary Search-->Trovo valore o indice del figlio su cui cercare
			while (a < b) {
				int pivot = (a + b) / 2;
				int res = key.compareTo((K) keys.get(pivot).getKey());
				if (res == 0)
					return (V) keys.get(pivot).getValue();
				else if (res < 0)
					b = pivot ;// Stessa modifica di prima
				else
					a = pivot + 1;
			}
			if(root.getChildren().size()==0)
				return null;
		
			return searchRec(root.getChildren().get(a), key);
		}
	}

	/**
	 * Metodo per la cancellazione di una chiave da un sottoalbero di radice node assicurando di scendere su un figlio che non ha il numero minimo di chiavi
	 * 
	 * @param node nodo in cui eleminare la chiave
	 * @param key chiave da eliminare
	 */
	private void deleteNonMin(TreeNode<K,V> node, K key) {
		// Utilizzando una ricerca dicotomica cerco la chiave
		int a = 0;
		int b = node.getSize();
		ArrayList<TInfo<K,V>> keys = node.getKeys();
		// Trovo valore o indice del figlio su cui cercare
		boolean found = false;
		int pivot = 0;
		while (a < b && !found) {
			pivot = (a + b) / 2;
			int res = key.compareTo((K) keys.get(pivot).getKey());
			if (res == 0)
				found = true;
			else if (res < 0)
				b = pivot ;
			else
				a = pivot + 1;
		}

		if (found) {
			int posChiave = pivot;
			// Ho trovato la chiave nel nodo
			if (node.isLeaf()) {
				// Sono in una foglia e posso rimuovere key
				node.removeKey(posChiave);
			} else {
				// Non sono in una foglia
				
				// Prendo il figlio sinistro rispetto alla chiave da eliminare
				TreeNode<K,V> child = node.getChildren().get(posChiave);
				// Se il figlio ha il numero minimo di chiavi lo incremento in
				// modo che posso prendermi una chiave da lui e portarla nel nodo in cui dobbiamo eliminare key
				if (child.getSize() == t - 1)
					augumentChild(node, posChiave);
				// Devo controllare il risultato della augumentChild
				// Possiamo avere tre casi: posChiave shiftato a sinistra di uno e quindi dobbiamo 
				// aggiornare la chiave; key viene spostato nel figlio e occorre richiamare la deleteNonMin
				// su questo sottoalbero; key è rimasto in node e devo spostare la chiave massima del 
				// figlio sinistro
				if (posChiave > 0
						&& node.getKeys().get(posChiave - 1).getKey().compareTo(key) == 0) {
					// AugumentChild ha riunito il figlio in posizione posChiave
					// col fratello sinistro prendendo un elemento dal padre (per questo posChiave è shiftato di -1)
					// aggiorno posChiave
					posChiave--;
				}
				if (node.getKeys().get(posChiave).getKey().compareTo(key) != 0) {
					// AugumentChild ha spostato key nel figlio di posizione
					// posChiave
					deleteNonMin(node.getChildren().get(posChiave), key);
				} else {
					// key è rimasto in node. Devo spostare la chiave massima
					// del sottoalbero con radice node.childeren[posChive]
					deleteMax(node, posChiave, node.getChildren()
							.get(posChiave));
				}
			}
		} else {
			// Key non è in node
			// Può stare nel sottoalbero con radice node.children[a]
			TreeNode<K,V> child = node.getChildren().get(a);
			if (child.getSize() == t - 1) {
				augumentChild(node, a);
				if (a > 0
						&& node.getKeys().get(a - 1).getKey().compareTo(key) >= 0) {
					// AugumentChild ha unito il figlio da incrementare col
					// fratello sinistro
					a--;
				}
			}
			deleteNonMin(node.getChildren().get(a), key);
		}
	}
	
/**
     * Sposta la massima chiave del sottoalbero di radice subTreeRoot in
	 * node.keys[i]
	 * 
	 * @param node Il nodo in cui verrà spostata la massima chiave del sottoalbero
	 * @param i posizione di node in cui verrà spostata la chiave
	 * @param subTreeRoot radice del sottoalbero in cui cercare la chiave massima
	*/
	private void deleteMax(TreeNode<K,V> node, int i, TreeNode<K,V> subTreeRoot) {

		if (subTreeRoot.isLeaf()) {
			// Se è foglia prendo la chiave massima e la sposto
			node.getKeys().set(i,
					subTreeRoot.getKeys().get(subTreeRoot.getSize() - 1));
			subTreeRoot.removeKey(subTreeRoot.getSize() - 1);

		} else {
			// Trovo la foglia con chiave massima e poi la sostituisco
			TreeNode<K,V> child = subTreeRoot.getChildren().get(
					subTreeRoot.getSize());
			if (child.getSize() == t - 1) {
				// Devo prima aumentare la dimensione del figlio
				augumentChild(child, subTreeRoot.getSize());
			}
			// Essendo l'ultimo figlio destro la chiave scenderà sicuro
			// nell'ultimo figlio destro
			deleteMax(node, i, child);
		}

	}

	/**
	 * Aumenta il numero di chiavi del nodo specificato prendendone una dai
	 * fratelli adiacenti. Se i fratelli adiacenti hanno tutti il minimo numero
	 * di chiavi allora riunisce il figlio con uno dei fratelli adiacenti e
	 * prende una chiave dal padre per rispettare l'ordinamento. Precondizioni:
	 * Node ha soltanto t-1 chiavi. Possiamo suddividere il problema in tre casi: 
	 * caso1 figlio da incrementare ha un fratello alla sua sinistra con dim non minima; 
	 * caso2 figlio da incrementare ha un fratello alla sua destra con dim non minima;
	 * caso3 i fratelli o l'unico fratello del figlio da incrementare avranno t-1 chiavi (dim minima) 
	 * 
	 * @param node Il nodo padre del figlio su cui operare
	 * @param childToAugument L'indice del figlio su cui operare
	 */
	
	private void augumentChild(TreeNode<K,V> node, int childToAugument) {
		TreeNode<K,V> brother;
		TreeNode<K,V> child = node.getChildren().get(childToAugument);
		//Caso 1 
		if (childToAugument > 0
				&& node.getChildren().get(childToAugument - 1).getSize() > t - 1) {
			// allora il figlio ha un fratello alla sua
			// sinistra
			brother = node.getChildren().get(childToAugument - 1);
			// allora si può prendere una chiave
			// dal fratello sinistro

			// Porto chiave padre in figlio e chiave fratello in padre
			child.addKey(0, node.getKeys().get(childToAugument - 1));
			node.getKeys().set(childToAugument - 1,
					brother.getKeys().get(brother.getSize() - 1));
			// Rimuovo la chiave appena aggiunta nel padre dal fratello del
			// figlio da aumentare
			brother.removeKey(brother.getSize() - 1);
			// Sposto anche i riferimenti nel figlio e aggiungo l'ultimo
			// riferimento del fratello
			if (!child.isLeaf()) {
				child.addChild(0, brother.getChildren().get(brother.getSize()));
				brother.removeChild(brother.getSize());
			}
		
			//Caso 2
		} else if (childToAugument < node.getSize()
				&& node.getChildren().get(childToAugument + 1).getSize() > t - 1) {

			// il figlio da incrementare ha un fratello destro di dimensione non
			// minima

			brother = node.getChildren().get(childToAugument + 1);
			// Posso prendere una chiave dal figlio destro
			// Porto chiave padre nel figlio da incrementare
			child.addKey(child.getSize(), node.getKeys().get(childToAugument));
			// Porto nel padre la prima chiave del fratello destro
			node.getKeys().set(childToAugument, brother.getKeys().get(0));
			// Rimuovo la chiave appena aggiunta nel padre dal fratello del
			// figlio da aumentare
			brother.removeKey(0);
			// Sposto anche i riferimenti
			if (!brother.isLeaf()) {
				child.addChild(child.getSize(), brother.getChildren().get(0));
				brother.removeChild(0);
			}

		} else {//Caso 3 unisco i due fratelli
			// I fratelli o l'unico fratello avranno t-1 chiavi
			int parentKeyToMove;

			if (childToAugument < node.getSize()) {//caso 3.1 esiste un figlio destro
				// Allora esisterà un fratello destro con t-1 chiavi
				// Possiamo unire i due fratelli
				brother = node.getChildren().get(childToAugument + 1);
				parentKeyToMove = childToAugument;
			} else {//caso 3.2 esiste un figlio sinistro
				// Allora ci sarà un fratello sinistro con t-1 chiavi
				// possiamo unire i due fratelli
				brother = node.getChildren().get(childToAugument - 1);
				parentKeyToMove = childToAugument - 1;
			}

			// Aggiungo la chiave del padre al figlio da incrementare
			child.addKey(t - 1,
					node.getKeys().get(parentKeyToMove));
			// Rimuovo la chiave spostata dal padre
			node.removeKey(parentKeyToMove);
		
			// Elimino il riferimento in eccesso nel padre
			node.removeChild(parentKeyToMove+1);

			// Sposto le chiavi del fratello destro nel figlio da
			// incrementare
			for (int i = 0; i < brother.getSize(); i++)
				child.addKey(i + t, brother.getKeys().get(i));
			// Sposto i riferimenti del fratello destro nel figlio da
			// incrementare
			if (!brother.isLeaf()) {
				for (int i = 0; i < brother.getSize() + 1; i++)
					child.addChild(i + t,brother.getChildren().get(i));
			}
			
		}
	

	}
	
	/**
	  * Metodo di interfaccia per verificare l'ordinamento dei nodi dell'albero
	  * 
	  * @return valore booleano che indica se l'albero è ordinato (TRUE) o meno (FALSE)
	  */
	 public boolean isOrder(){
		 boolean ord=true;
		 return OVerification(root,ord);
	 }
	 
	 
	/**
	  * Metodo concreto per la verifica dell'ordinamento dei nodi dell'albero
	  * 
	  * @param root nodo di partenza per verificare l'ordinamento
	  * @param ord 
	  * @return
	  */
	 public boolean OVerification(TreeNode<K,V> root, boolean ord){
		 if (root == null) 
		      return true;
		  else{
			  
			  ArrayList<TInfo<K,V>> keys=root.getKeys();
		  
			  for(int i=0;i<keys.size()-1;i++){
				  if(keys.get(i).getKey().compareTo(keys.get(i+1).getKey())>0)
					  return false;
			  }
			 
			  for(int j=0;j<root.getChildren().size();j++){
				  ord=OVerification(root.getChildren().get(j),ord); 		    	
			  }
		    	
		 return ord;		 
		  }
	 }
	
}




